package main

import (
	"fmt"
	"sort"
)

func main() {
	fmt.Println(permutation2("aabbc"))
}

//func permutation(str []rune, start int) {
//	if start == len(str)-1 {
//		fmt.Println(string(str))
//	} else {
//		for i := start; i < len(str); i++ {
//			if !isD
//		}
//	}
//}
func permutation2(s string) (ans []string) {
	t := []byte(s)
	sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
	n := len(t)
	perm := make([]byte, 0, n)
	vis := make([]bool, n)
	var backtrack func(int)
	backtrack = func(i int) {
		if i == n {
			ans = append(ans, string(perm))
			return
		}
		for j, b := range vis {
			if b || j > 0 && !vis[j-1] && t[j-1] == t[j] {
				continue
			}
			vis[j] = true
			perm = append(perm, t[j])
			backtrack(i + 1)
			perm = perm[:len(perm)-1]
			vis[j] = false
		}
	}
	backtrack(0)
	return
}

func permutation(str string) []string {
	var ans []string
	var permutationHelper func([]byte, []byte)
	bytesIn := []byte(str)
	fastSort(bytesIn)
	permutationHelper = func(bytes []byte, path []byte) {
		if len(bytes) == 0 {
			ans = append(ans, string(path))
		}
		for i := 0; i < len(bytes); i++ {
			if (i > 0 && bytes[i] == bytes[i-1]) || (i != 0 && bytes[0] == bytes[i]) {
				continue
			}
			bytes[0], bytes[i] = bytes[i], bytes[0]
			path = append(path, bytes[0])
			if len(bytes) == len(bytesIn) {
				fmt.Printf("%v ", string(bytes))
			}
			permutationHelper(bytes[1:], path)
			path = path[:len(path)-1]
			bytes[0], bytes[i] = bytes[i], bytes[0]
			if len(bytes) == len(bytesIn) {
				fmt.Print(string(bytes), " ")
			}
		}
	}
	permutationHelper(bytesIn, []byte{})
	return ans
}

func fastSort(input []byte) {
	if len(input) <= 1 {
		return
	}
	mid := input[0]
	var i, j int
	for i, j = 1, len(input)-1; i < j; {
		for ; i <= j && input[i] <= mid; i++ {
		}
		for ; i <= j && input[j] > mid; j-- {
		}
		if i < j {
			input[i], input[j] = input[j], input[i]
		}
	}
	input[0], input[j] = input[j], input[0]
	fastSort(input[:j])
	fastSort(input[i:])
}
